Codeforces Round #216 (Div. 2)

A

讨论对于每一天吃饭需不需要洗餐具即可,优先使用盘子,其次使用碗,都没有就洗一个。

时间复杂度 O(n)O(n)

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;

int n, m, k, ans, a[N];

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        if (a[i] == 1) m ? m-- : ans++;
        if (a[i] == 2) k ? k-- : m ? m-- : ans++;
    }
    cout << ans << endl;
}

B

按照 a1a2ana_1\ge a_2\ge\cdots\ge a_n 的顺序安排,先求出 i=k+1nai\sum\limits_{i=k+1}^n a_i 并安排 [k+1,n][k+1,\,n] ,然后再安排 [1,k][1,\,k] 即可。

时间复杂度 O(n)O(n) ,注意 n=kn=k 的特殊情况。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;

int n, k, l, r, S_all, S_k;
int a[N], S_res;

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> k >> l >> r >> S_all >> S_k;
    if (n != k) {
        S_res = S_all - S_k;
        for (int i = k + 1; i <= n; i++) a[i] = l;
        S_res -= (n - k) * l;
        for (int i = k + 1; i <= n; i++) a[i] += S_res / (n - k);
        S_res %= (n - k);
        for (int i = k + 1; i <= k + S_res; i++) a[i]++;
        for (int i = 1; i <= k; i++) a[i] = a[k + 1];
        S_k -= k * a[k + 1];
        for (int i = 1; i <= k; i++) a[i] += S_k / k;
        S_k %= k;
        for (int i = 1; i <= S_k; i++) a[i]++;
    } else {
        for (int i = 1; i <= n; i++) a[i] = S_all / n;
        S_all %= n;
        for (int i = 1; i <= S_all; i++) a[i]++;
    }
    for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n];
}

C

维护一个答案集合 SS ,在搜索过程中维护修复根结点到 uu 路径上所有问题边所需要选中的结点 xx,如果边 (u,v)(u,v) 为问题边则将 xxSS 中删除并加入 vv

时间复杂度 O(nlogn)O(n\log{n})

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

struct edge {
    int v, next, w;
    edge(): v(0), next(0), w(0) {}
    edge(int v, int next, int w): v(v), next(next), w(w) {}
} e[N];

int p[N], dep[N], n, eid;
set<int> st;

inline void insert(int u, int v, int w) {
    e[eid] = edge(v, p[u], w);
    p[u] = eid++;
}

void dfs(int u, int fa, int mn) {
    for (int i = p[u]; i != -1; i = e[i].next) {
        int v = e[i].v;
        if (v == fa) continue;
        if (e[i].w) {
            st.erase(mn);
            st.insert(v);
            dfs(v, u, v);
        }
        else dfs(v, u, mn);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    memset(p, -1, sizeof(p));
    for (int i = 1; i <= n - 1; i++) {
        int u, v, t;
        cin >> u >> v >> t;
        t--;
        insert(u, v, t);
        insert(v, u, t);
    }
    dfs(1, 1, 1);
    cout << st.size() << endl;
    for (int it : st) cout << it << " ";
}

D

注意到局面的改变只与编号最小的两个人有关,考虑dp。设 fi,jf_{i,j} 为幸存者编号最小值为 ii ,次小值为 jj 的局面出现的最小轮数。

由于需要快速判断 ii 是否有可能被后面的人打死,考虑维护 pp 的后缀最大值 sufi=maxj=inpisuf_i=\max\limits_{j=i}^n p_i ,讨论最大值和最小值的更新方法,从而得到转移方程:

  • ii 被打死且 jj 存活,需要满足 pi<1p_i<1sufj>0suf_j>0 ,此时有转移

fj,j+1=min{fj,j+1,fi,j+1}f_{j,j+1}=\min\{f_{j,j+1},\,f_{i,j}+1\}

  • ii 打死 jjii 存活,需要满足 sufj<1suf_j<1pi>0p_i>0 ,此时有转移

fi,j+1=min{fi,j+1,fi,j+1}f_{i,j+1}=\min\{f_{i,j+1},\,f_{i,j}+1\}

  • iijj 都被打死,需要满足 sufj>0suf_j>0pi>0p_i>0 ,此时有转移

fj+1,j+2=min{fj+1,j+2,fi,j+1}f_{j+1,j+2}=\min\{f_{j+1,j+2},\,f_{i,j}+1\}

最后统计所有情况中最小轮数小于等于 kk 的即可,时间复杂度 O(n2)O(n^2)

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 3005;

int f[N][N], p[N], suf[N], n, k, ans;

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> p[i];
    memset(f, 0x3f, sizeof(f));
    for (int i = n; i >= 1; i--) suf[i] = max(suf[i + 1], p[i]);
    f[1][2] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            int v = f[i][j] + 1;
            if (suf[j] && p[i] != 100) f[j][j + 1] = min(f[j][j + 1], v);
            if (suf[j] && p[i]) f[j + 1][j + 2] = min(f[j + 1][j + 2], v);
            if (suf[j] != 100 && p[i]) f[i][j + 1] = min(f[i][j + 1], v);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n + 1; j++)
            ans += (f[i][j] <= k);
    }
    cout << ans + (f[n + 1][n + 2] <= k) << endl;
}

E

待补。

赞赏